﻿//Write a program that finds in given array of integers a sequence of given sum S (if present).
//Example:	 {4, 3, 1, 4, 2, 5, 8}, S=11 -> {4, 2, 5}


using System;

public class SequenceOfMaximalSum
{
    public static void Main()
    {
        Console.Write("Enter the number of elements of the array: ");
        int elementsCount = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter {0} elements of the array", elementsCount);
        int[] array = new int[elementsCount];
        for (int i = 0; i < elementsCount; i++)
        {
            array[i] = int.Parse(Console.ReadLine());
        }
        int sum = int.Parse(Console.ReadLine());
        int tempSum = array[0];
        int begin = 0;
        int beginTemp = 0;
        int end = 0;
        for (int i = 1; i < array.Length; i++)
        {
            if (tempSum < 0)
            {
                tempSum = array[i];
                beginTemp = i;
            }
            else
            {
                tempSum += array[i];
            }
            if (tempSum == sum)
            {
                sum = tempSum;
                begin = beginTemp;
                end = i;
            }
        }
        Console.Write("Sum = {0} -> {{", sum);
        for (int i = begin; i <= end; i++)
        {
            if (i < end)
            {
                Console.Write("{0}, ", array[i]);
            }
            else
            {
                Console.Write("{0}", array[i]);
            }
        }

        Console.WriteLine('}');
    }
}